package com.xiaoyu.dp;

/**
 * @program: DS_and_A
 * @description: 最长回文子串
 *
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 * @author: YuWenYi
 * @create: 2021-05-25 09:36
 **/
public class LongestPalindrome_5 {

    //这的确是一种可行的方案,但是,这由于双重for循环,它的时间复杂度较高,因此LeetCode会报出超时!
    public String longestPalindrome(String s) {
        int len = s.length();
        for (int i = len ; i > 0; i--) {  //长度从5减到1,来一个个找"回文子串",找到就立刻返回
            for (int j = 0; j < len; j++) {
                if (i+j>len){
                    break;
                }
                String substr = s.substring(j,i+j);  //i+j-j == i,即需要固定长度的字符串,i+j用于滚动所需的字符串
                if (isPalindrome(substr)){
                    return substr;
                }
            }
        }
        return "";
    }
    public boolean isPalindrome(String substr){
        int len = substr.length();
        if (len == 1) return true;
        StringBuilder sb = new StringBuilder(substr);
        StringBuilder rev = sb.reverse();
        return substr.equals(rev.toString());
    }


    //方法二:使用动态规划! 我们用 P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串是否为回文串
    //容易得出:转移方程为:P(i,j) = P(i+1,j-1) & (S(i) == S(j))  s.len > 3
    //当s.len == 1的时候,P(i) = true ,当s.len == 2的时候,P(i,i+1) = S(i) == S(i+1)
    public String longestPalindrome1(String s) {
        int len = s.length();
        //特殊判断
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示s[i...j] 是否是回文串
        boolean[][] dp = new boolean[len][len];

        //初始化
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        // 3. 状态转移
        // 注意：先填左下角
        // 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j ; i++) {
                // 头尾字符不相等，不是回文串
                if (s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    // 相等的情况下
                    // 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
                    if (j - i < 3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];  //一般情况就需要进行状态转移
                    }
                }

                // 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
                // 此时更新记录回文长度和起始位置
                // 注意,需要在新的长度大于原来的长度的时候,更新才有意义!
                if (dp[i][j] && j-i+1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }

            }
        }
        return s.substring(begin, begin+maxLen);  //由于substring是左开右闭,因此需要右边是begin+maxLen
    }

    public static void main(String[] args) {
        LongestPalindrome_5 l5 = new LongestPalindrome_5();
        System.out.println(l5.longestPalindrome1("cccc"));
    }
}
